CS137复习大纲

目录

数据结构

  1. 链表
  2. 双向链表
  3. 栈
  4. 队列
  5. 优先队列
  6. 基本二叉树
  7. 通用树
  8. 堆
  9. 哈希表
  10. 红黑二叉树
  11. 平衡二叉树

排序算法

  1. 冒泡排序 Bubble sort
  2. 插入排序 Insertion sort
  3. 选择排序 Selection sort
  4. 希尔排序 Shell sort
  5. 归并排序 Merge sort
  6. 快速排序 Quick sort
  7. 堆排序 Heap sort
  8. 计数排序
  9. 桶排序 Bucket sort
  10. 基数排序 Radix sort

类

  1. 类的定义
  2. 类的创建（构造函数）
  3. 类的销毁（析构函数）
  4. 类的继承
  5. 类的方法
  6. 类的重载

数据结构

表（List）

<20, 23 | 12, 15>
| 表示 fence, <>表示头节点和尾节点

List ADT

template <class Elem> class List { 
public:
    virtual void clear() = 0; 
    virtual bool insert(const Elem&) = 0; 
    virtual bool append(const Elem&) = 0; 
    virtual bool remove(Elem&) = 0; 
    virtual void setStart() = 0; 
    virtual void setEnd() = 0; 
    virtual void prev() = 0; 
    virtual void next() = 0; 
    virtual int leftLength() const = 0; 
    virtual int rightLength() const = 0; 
    virtual bool setPos(int pos) = 0; 
    virtual bool getValue(Elem&) const = 0; 
    virtual void print() const = 0;
};

基于Array的List

插入



类实现
template <class Elem> class AList : public List<Elem> { 
private: 
    int maxSize; // Maximum size of list 
    int listSize; // Actual elem count 
    int fence; // Position of fence
    Elem* listArray; // Array holding list 
public:
    AList(int size=DefaultListSize) { 
        maxSize = size; 
        listSize = fence = 0; 
        listArray = new Elem[maxSize];
    }
    ~AList() { delete [] listArray; }
    void clear() {
        delete [] listArray; 
        listSize = fence = 0; 
        listArray = new Elem[maxSize];
    } 
    void setStart() { fence = 0; } 
    void setEnd() { fence = listSize; } 
    void prev() { if (fence != 0) fence--; } 
    void next() { if (fence <= listSize) fence++; }
    int leftLength() const { return fence; } 
    int rightLength() const { return listSize - fence; }
    bool setPos(int pos) {
        if ((pos >= 0) && (pos <= listSize))
        fence = pos; 
        return (pos >= 0) && (pos <= listSize);
    }
    bool getValue(Elem& it) const {
        if (rightLength() == 0) return false; 
        else {
            it = listArray[fence]; return true;
        }
    }
    bool insert(const Elem&); 
    bool append(const Elem&); 
    bool remove(Elem&);
};
复杂度
操作 复杂度
Append \(O(1)\)
Find \(O(n)\)
Delete \(O(n)\)
GeitByIndex \(O(1)\)
Insert \(O(n)\)

链表

单向链表

结构图



类实现
// Singly-linked list node
template <class Elem> class Link { 
public:
    Elem element; // Value for this node
    Link * next; // Pointer to next node
    Link(const Elem& elemval, Link* nextval =NULL){ 
        element = elemval; 
        next = nextval; 
    }
    Link(Link* nextval =NULL){ next = nextval; }
};

template <class Elem> class LList:public List<Elem> {
private:
    Link<Elem>* head, tail, fence; 
    int leftcnt, int rightcnt;
    void init() { // Initialization routine
        fence = tail = head = new Link<Elem>; 
        leftcnt = rightcnt = 0;
    }
    void removeall() {//Return link nodes back to free store
        while(head != NULL) { 
            fence = head; 
            head = head->next; 
            delete fence;
        }
    }
public:
    LList(int size=DefaultListSize) { init(); }
    ~LList() { removeall(); } //Destructor 
    void clear() { removeall(); init(); } 
    bool insert(const Elem&); 
    bool append(const Elem&); 
    bool remove(Elem&); 
    void setStart() {
        fence = head; 
        rightcnt += leftcnt;
        leftcnt = 0;
    }
    void setEnd() {
        fence = tail; 
        leftcnt += rightcnt;
        rightcnt = 0;
    }
    void prev(); void next() {
        // Don't move fence if right empty 
        if (fence != tail) {
            fence = fence->next; 
            rightcnt--;
            leftcnt++; 
        }
    }
    int leftLength() const { return leftcnt; }
    int rightLength() const { return rightcnt; } 
    bool getValue(Elem& it) const {
        if(rightLength() == 0) return false; 
        it = fence->next->element; 
        return true; 
    }
    void print () const;
};
复杂度
操作 复杂度
Append \(O(1)\)
Find \(O(n)\)
Delete \(O(n)\)
FindByIndex \(O(n)\)
Insert \(O(1)\)

双向链表

比起单向链表，多了一个前驱指针。其删除操作的时间复杂度降到了\(O(1)\)， 代价是浪费了春初空间。

类实现
template <class Elem> class Link
{
private:
    static Link<Elem> *freelist;               
    static unsigned long freelistCount;         
public:
    Elem element;                               
    Link * next;                                 
    Link * prev;                                 
    Link(const Elem&, Link *prevp = nullptr, Link *nextp = nullptr);
    Link(Link *prevp = nullptr, Link *nextp = nullptr);
    void * operator new(size_t);                
    void operator delete(void *);
};

template <class Elem> class DLList : public List<Elem>
{
private:
    Link<Elem> *head;               // Point to list header
    Link<Elem> *tail;               // Pointer to last Elem in list
    Link<Elem> *fence;              // Last element on left side
    unsigned long leftcnt;
    unsigned long rightcnt;
    void init();
    void removeall();
    bool expand(unsigned long);
    static unsigned long freelistLimit;
    
public:
    DLList(unsigned long size = DEFAULT_LIST_SIZE);        
    ~DLList();             
    void clear();        
    bool insert(const Elem&);        
    bool append(const Elem&);
    bool remove(Elem&);        
    void setStart()  ;     
    void setEnd();        
    void prev();        
    void next();        
    unsigned long leftLength() const;        
    unsigned long rightLength() const;      
    bool setPos(unsigned long);        
    bool getValue(Elem&) const;        
    void print() const;
};
复杂度
操作 复杂度
Append \(O(1)\)
Find \(O(n)\)
Delete \(O(1)\)
FindByIndex \(O(n)\)
Insert \(O(1)\)

栈 Stack

特性：先进先出

Stack ADT
template <class Elem> class Stack { 
public:
    // Reinitialize the stack 
    virtual void clear() = 0;
    // Push an element onto the top of the stack.
    virtual bool push(const Elem&) = 0; 
    // Remove the element at the top of the stack. 
    virtual bool pop(Elem&) = 0;
    // Get a copy of the top element in the stack v
    irtual bool topValue(Elem&) const = 0; 
    // Return the number of elements in the stack.
    virtual int length() const = 0;
};

可以基于数组也可以基于链表实现

复杂度
操作 复杂度
Append \(O(1)\)
Find -
Delete \(O(1)\)
FindByIndex -
Insert -
C++ STL
#include <stack>
#include <vector>
std::stack<Typename> Stack;

empty() 测试栈是否为空，为空返回true，否则返回false。
size() 返回栈中元素的个数
top() 返回栈顶元素(最后push进来的那个)的引用。
push(val) 压一个值到栈中，其值将被初始化为 val
pop() 将栈顶元素弹出，注意这个函数无返回值
emplace(Args..) emplace 功能上与 push相同。不过emplace更高效。
swap() swap将两个 stack的内容交换。这两个 stack的模板参数 T和 Container必须都相同。

队列 Queue

特性：先进先出

单向队列 Queue

复杂度
操作 复杂度
Append \(O(1)\)
Find -
Delete \(O(1)\)
FindByIndex -
Insert -
C++ STL
#include <queue>
#include <vector>
std::queue<Typename> Queue;

empty() 测试队是否为空，为空返回true，否则返回false。
size() 返回队中元素的个数
front() 访问队首
back() 访问队尾
push(val) 压一个值到队尾，其值将被初始化为 val
pop() 将队首元素弹出，注意这个函数无返回值
emplace(Args..) emplace 功能上与 push相同。不过emplace更高效。
swap() swap将两个 stack的内容交换。这两个 stack的模板参数 T和 Container必须

双向队列 Dequeue

特性：两边都可以进出

复杂度
操作 复杂度
Append \(O(1)\)
Find -
Delete \(O(1)\)
FindByIndex -
Insert -
C++ STL
#include <deque>
#include <vector>
std::deque<Typename> Deque;

empty() 测试队是否为空，为空返回true，否则返回false。
size() 返回队中元素的个数
front() 访问队首
back() 访问队尾
push_front(val) 压一个值到队首，其值将被初始化为 val
push_back(val) 压一个值到队尾，其值将被初始化为 val
pop_front() 将队首元素弹出，注意这个函数无返回值
pop_back() 将队尾元素弹出，注意这个函数无返回值
emplace(Args..) emplace 功能上与 push相同。不过emplace更高效。
swap() swap将两个 stack的内容交换。这两个 stack的模板参数 T和 Container必须

其他

erase()
clear()
insert()
at()

优先队列 Priority Queue

本质上是维护一个堆（Heap），使得每次出队的元素优先度最大

基本二叉树

基本符号

node
children
edge
parent
ancestor
descendant
path 长度定义为edge的数量，方向是从浅节点到深节点
depth 根节点的深度为0
height 最深的节点的深度+1
level
leaf node 没有children的node
internal node 有children的 node
subtree

定义

满二叉树（Full binary tree）： 所有的internal node都有两个节点


全二叉树（Complete binary tree）：height - 1 层的节点都是满的


定理

The number of leaves in a non-empty full binary tree is one more than the number of internal nodes

The number of null pointers in a non-empty tree is one more than the number of nodes in the tree.

Binary node ADT

template <typename E> class BinNode { 
public:
    // Return the node’s value 
    virtual E& val() = 0; 
    // Set the node’s value 
    virtual void setVal(const E&) = 0; 
    // Return the node’s left child 
    virtual BinNode* left() const = 0;
    // Set the node’s left child 
    virtual void setLeft(BinNode*) = 0; 
    // Return the node’s right child 
    virtual BinNode* right() const = 0; 
    // Set the node’s right child 
    virtual void setRight(BinNode*) = 0;
    // Return true if the node is a leaf, false otherwise 
    virtual bool isLeaf() = 0;
};

遍历


如图

层序遍历 Level-order traversal

顾名思义，一层一层遍历节点
FBGADICEH

先序遍历 Preorder traversal

先访问根节点，再访问子节点
FBADCEGIH

后序遍历 Postorder traversal

先访问左子树，再访问右子树，最后访问根节点
ACEDBHIGF

中序遍历 Inorder traversal

先访问左子树，再访问根节点，最后访问右子树
ABCDEFGHI

遍历树的C++实现（递归）

Preorder
template <class Elem>
void preorder(BinNode<Elem>* subroot) {
if (subroot == NULL) return; // Empty 
visit(subroot); // Perform some action 
preorder(subroot->left()); 
preorder(subroot->right());
}
【施工中】Inorder
【施工中】Postorder

遍历树的C++实现（非递归）

【施工中】

哈夫曼编码Huffman Coding

背景
一些定义

若规定根结点的层数为\(1\)，则从根结点到第\(L\)层结点的路径长度为\(L-1\)。

操作
  1. 首先统计字符出现的频率
  2. 以频次作为参考，建立哈夫曼编码树，该树有如下特点：
    1. 有\(n\)个内节点（权值）就有\(n+1\)个叶节点
    2. 每个内节点都有两个子节点
    3. 每个内节点的权值等于其两个子节点权值之和
  3. 根据不同节点的位置，赋予它们编码
      
Letter Freq Code Bit
C 32 1110 4
D 42 101 3
E 120 0 1
M 24 11111 5
K 7 111101 6
L 42 110 3
U 37 100 3
Z 2 111100 6
解码

对于输入的二进制码，借助已经生成的哈夫曼树（字典）解码（相当于搜索树）。成功解码一个字符后立刻开始下一个字符的解码

Example
Code for ‘DEED’：10100101
Decode for ‘1011001110111101’：DUCK

区分叶节点LeafNode和内节点IntlNode

  1. 通过继承实现
  2. 设计一个isLeaf()来实现

二叉树的一些操作

镜像

遍历所有内节点，然后交换每个节点的左右子树
只要完成遍历即可，不必苛求何种遍历

搜索树Binary Search Tree

二叉搜索树有如下特征：

二叉搜索树在使用时要处理好Remove和Insert操作，他们的复杂度在平衡（理想）情况下都是\(O(\log n)\)

二叉树的线性表示



对于满二叉树（Full binary trees），使用‘ / 等符号表示叶节点和内部节点，如
A’B’/DC’E’G/F’HI
'代表有子结点，/代表空指针，无'代表无子结点

疑问：
该方法只能用于Full binary trees嘛

对于一般的二叉树，用/表示空链接（null links）
AB/D//CEG///FH//I//

堆

堆可以分为小顶堆和大顶堆
小顶堆，小的元素在上；大顶堆，大的元素在上

堆的实质是一颗二叉树。该二叉树的每一个节点的左子节点都比右子节点小（或者大，取决于具体实现）

堆的另一个特性是它除了最深一层外，每一层都是满的。给予这个特性，我们可以用数组来表示一个堆。对于一个节点，我们这样定义他的parent，leftchild，rightchild

int leftchild(int pos) const { return 2*pos+1; }
int rightchild(int pos) const { return 2*pos+2; }
int parent(int pos) const { return (pos-1)/2; }

堆的C++实现

// This heap has a fixed size, it drops values when adding new ones
template <class Elem, class Comp>
class SlidingHeap{
private:
    int size;
    int n;
    void shiftdown(int);
    void swap(int pos1, int pos2);
public:
    Elem * heap;
    
    // constructors, must define the copy constructor because it need to be copy-passed to saveHeap() in order to print sentences in the order of hash values
    SlidingHeap(int max){ n=0; size = max; heap = new Elem[max];}
    SlidingHeap(const SlidingHeap& H) {
        heap = new Elem[H.size];
        size = H.size;
        n = H.n;
        for (int i = 0; i < size; i++) { heap[i] = H.heap[i]; } 
    }
    SlidingHeap(){}
    
    // destructor
    ~SlidingHeap(){ delete[] heap;}
    
    // Besides insert(), the rest of the implementation is similar to the demo code
    int heapsize() const;
    bool isLeaf(int pos) const {return (pos>=n/2) && (pos<n); }
    int leftchild(int pos) const { return 2*pos+1; }
    int rightchild(int pos) const { return 2*pos+2; }
    int parent(int pos) const { return (pos-1)/2; }
    bool insert(const Elem&);
    bool removemax(Elem&);
    bool remove(int, Elem&);
    void buildheap(){ for (int i=n/2-1; i>=0; i--) shiftdown(i); }
    void print(){ for(int i=0; i<n; i++){ std::cout << " | " << heap[i]; } std::cout << " | \n";}
};

shiftdown()操作将位于堆顶的元素安置到合适的位置

template <class Elem, class Comp>
void SlidingHeap<Elem, Comp>::shiftdown(int pos){
    while (!isLeaf(pos)) {
        int j = leftchild(pos);
        int rc = rightchild(pos);
        if (rc<n and Comp::lt(heap[j], heap[rc])) j = rc;
        if (!Comp::lt(heap[pos], heap[j])) return;
        swap(pos,j);
        pos = j;
    }
}

insert()用于插入元素,做法是：

template <class Elem, class Comp>
bool SlidingHeap<Elem, Comp>::insert(const Elem& val){
    
    // if the heap is full, decide whether to drop the input or the top element.
    if (n >= size) {
        if (Comp::gt(heap[0],val)) {
            heap[0] = val;
            shiftdown(0);
            return true;
        } else {
            return false;
        }
    }
    int curr = n++;
    heap[curr] = val;
    while ((curr != 0) and (Comp::gt(heap[curr], heap[parent(curr)]))) {
        swap(curr, parent(curr));
        curr = parent(curr);
    }
    return false;
}

template <class Elem, class Comp>
bool SlidingHeap<Elem, Comp>::removemax(Elem& it){
    if (n == 0) return false;
    swap(0, --n);
    if (n != 0) shiftdown(0);
    it = heap[n];
    return true;
}

堆的复杂度

建堆的复杂度为\(O(n)\)

证明

bottom-up建堆。有1/2的元素向下比较了一次，有\(\frac{1}{4}\)的向下比较了两次，\(\frac{1}{8}\)的，向下比较了3次，......，\(\frac{1}{2^k}\)的向下比较了\(k\)次，其中\(\frac{1}{2^k} \leq 1\), k 约等于\(log(n)\)。于是就有总的比较量：
\(T = (\sum_{k=1}^{\log n} \frac{1}{2^k}\times n\)

令\(S = \sum_{k=1}^{\log n} \frac{1}{2^k}\)

\(\frac{1}{2}S = \sum_{k=1}^{\log n} \frac{1}{2^{k+1}} = \frac{1}{4} + \frac{1}{8}\times 2+ ··· + \frac{1}{2^{k+1}}\times k\)

\(S - \frac{1}{2}S = \frac{1}{2}S = \frac{1}{2} + \frac{1}{4} + ··· + \frac{1}{2^k}-\frac{1}{2^{k+1}} \times k\)

显然 \(S \leq 2\)

出堆的复杂度为\(O(\log n)\)

堆的应用

使用自定义结构的时候需要自己写一个比较类

哈希表 Hash table

哈希

哈希函数是一类泛函。它们接受特定的参数，输出一个整数。对于一个key-value键值对，我们可以计算出key对应的hash值，然后将value存储到相应的位置上。

ELF Hash Function
// ELF Hash Function  
unsigned int ELFHash(char *str)  
{  
    unsigned int hash = 0;  
    unsigned int x = 0;  
  
    while (*str)  
    {  
        hash = (hash << 4) + (*str++);//hash左移4位，把当前字符ASCII存入hash低四位。   
        if ((x = hash & 0xF0000000L) != 0)  
        {  
            //如果最高的四位不为0，则说明字符多余7个，现在正在存第8个字符，如果不处理，再加下一个字符时，第一个字符会被移出，因此要有如下处理。  
            //该处理，如果对于字符串(a-z 或者A-Z)就会仅仅影响5-8位，否则会影响5-31位，因为C语言使用的算数移位  
            //因为1-4位刚刚存储了新加入到字符，所以不能>>28  
            hash ^= (x >> 24);  
            //上面这行代码并不会对X有影响，本身X和hash的高4位相同，下面这行代码&~即对28-31(高4位)位清零。  
            hash &= ~x;  
        }  
    }  
    //返回一个符号位为0的数，即丢弃最高位，以免函数外产生影响。(我们可以考虑，如果只有字符，符号位不可能为负)  
    return (hash & 0x7FFFFFFF);  
}

Hash函数一直是人规定的。我们追求计算迅速，分布均匀（针对特定问题）的哈希函数。

哈希表

哈希表是为了实现字典而出现的
哈希表试图让查找的时间复杂度达到\(O(1)\)

Dictionary
// The Dictionary abstract class. template <class Key, class Elem,
class KEComp, class EEComp> class Dictionary {
public:
    virtual void clear() = 0;
    virtual bool insert(const Elem&) = 0; 
    virtual bool remove(const Key&, Elem&) = 0; 
    virtual bool removeAny(Elem&) = 0;
    virtual bool find(const Key&, Elem&) const = 0; 
    virtual int size() = 0;
};
Class hashdict : public Dictionary<Key, Elem, KEComp, EEComp>;

哈希表可能会冲突。\(H(k_1) = \beta = H(k_2)\)

Open hashing 可以解决这个问题：每个哈希表的项目都是一个桶（bin）




Bucket Hashing 有两个桶。当一个Hash table满了的时候，数据放在Overflow里。寻找的时候也是如此




Closed Hashing 把所有的记录都存在hash table里。当发生冲突的时候，我们根据某种方式找到新的位置。寻找的时候也是这样。这个过程叫做Probe。

线性探测（Linear Probing）只是简单地寻找下一个槽，为了避免循环探测，表必须始终保留一个非空的槽

改进的线性探测（Improved Linear Probing）跳过常数C个槽，最好让C和表长M互质。

Random Probing 实际上不可能实现。可以事先构建一系列伪随机数（Pseudo-random numbers）作为Prob的步长

也可以通过平方来探测如30，31，34，39，46...这样

二次哈希

可以用两种不同的函数求哈希值，当第一种出现冲突时，用第二种算出步长进行查找。

Example: Hash table of size M=101

删除

删除哈希表的元素时必须要小心：对于存在移位（Probe）的表，有必要让后面的元素继续保持可用。
一个好方法是防止里程碑（Tombstone）来代替被删除的元素。

通用树 General Tree

这是一个通用二叉树的结构




这样的结构没有办法很轻松地用程序实现，因为每个节点占用的内存空间都不同，我们用二叉树来实现通用树

每个节点都有value、parent、child、sibling四个attribute。就像这样


通用树的C++实现

节点

// General tree node ADT
template <class Elem> class GTNode { public:
    GTNode(const Elem&); // Constructor
    ~GTNode();
    Elem value();
    bool isLeaf();
    GTNode* parent();
    GTNode* leftmost_child(); 
    // First child GTNode* right_sibling(); 
    // Right sibling void setValue(Elem&); 
    // Set value void insert_first(GTNode<Elem>* n);
    void insert_next(GTNode<Elem>* n);
    void remove_first(); // Remove first child
};

树

// General tree
template <typename E> class GenTree {
private:
GTNode<E>* root; public:
    void clear(); // Send all nodes to free store
    GTNode<E>* root(); // Return the root of the tree
    // Combine two subtrees
    void newroot(E&, GTNode<E>*, GTNode<E>*);
    void print(); // Print a tree
};

树的遍历

General Tree的遍历实现可以有很多种。比如先遍历子一层，再遍历父一层。每层的兄弟节点间都有指针相连，灵活性很高。

只有parent指针的树

如果移除child、sibling，仍然可以利用parent这个属性组成一颗树

这样可以节约一些空间，代价是很难将整个树输出。

Union 操作

有些时候，我们希望通过Union操作将两个树合并在一起，一个简单的思路是：

  1. 寻找A的根结点find()
  2. 寻找B的根结点find()
  3. 将B的根结点添加到A的子节点中

我们还可以先判断A、B两树的规模，让规模小的树加入规模大的，从而保持总体的平衡。

Union操作的时间复杂度取决于find操作的时间复杂度。在没有路径压缩的情况下复杂度为\(O(n\log n)\)

Path compression

在Union操作中，find()操作会耗去很多时间。该操作与树的路径深度息息相关
如果我们能再每次find()操作中对路径进行压缩，就能够节约很多时间，如：

Point * find(Point * p) {
        while(not isRoot(*p)) {
            p->parent = p->parent->parent;
            p = p->parent;
        }
        return p;
    }

因此，find()操作的时间复杂度近似\(O(1)\)

杂种树

如果我们放宽parent的限制，从事实上让parent指针变为ancestor指针，我们就可以实现path compression（操作ancestor指针），并且能够轻松输出每棵树的成员（借助child sibling指针。

通用树的线性表示

用 )表示子节点的结束
RAC)D)E))BF)))
这里用到R表示根结点

红黑二叉树

平衡二叉树

排序

排序总结

算法 平均 最坏 最好 空间 稳定性 复杂度
Insertion Sort \(O(n^2)\) \(O(n^2)\) \(O(n)\) \(O(1)\) Stable Simple
Shell Sort \(O(n^{1.5})\) \(O(n^{1.5})\) \(O(n^{1.5})\) \(O(1)\) UnStable Complex
Bubble Sort \(O(n^2)\) \(O(n^2)\) \(O(n^2)\) \(O(1)\) Stable Simple
Quicksort \(O(n\log n)\) \(O(n^2)\) \(O(n\log n)\) \(O(\log n)\) Unstable Complex
Selection \(O(n^2)\) \(O(n^2)\) \(O(n^2)\) \(O(1)\) UnStable Simple
Heapsort \(O(n\log n)\) \(O(n\log n)\) \(O(n\log n)\) \(O(1)\) Unstable Complex
Mergesort \(O(n\log n)\) \(O(n\log n)\) \(O(n\log n)\) \(O(n)\) Stable Complex
Radix SOrt \(O(k(n+r))\) \(O(k(n+r))\) \(O(k(n+r))\) \(O(n+r)\) Stable Complex

冒泡排序 Bubble sort

原理

从头开始，对于每个位置，从未排序的数据中选取最优的


实现

情况 时间复杂度
最好 \(O(n^2)\)
最坏 \(O(n^2)\)
平均 \(O(n^2)\)

插入排序 Insertion sort

原理

从头开始，将i+1项向前插入到合适的位置



实现

template <class Elem, class Comp> 
void inssort(Elem A[], int n) {
    for (int i=1; i<n; i++) 
        for (int j=i; (j>0) &&(Comp::lt(A[j], A[j-1])); j--) 
            swap(A, j, j-1);
}
情况 时间复杂度
最好 \(O(n)\)
最坏 \(O(n^2)\)
平均 \(O(n^2)\)

选择排序 Selection sort

原理

和冒泡排序类似，但是减少了交换次数



实现

template <class Elem, class Comp> 
void selsort(Elem A[], int n) {
    for (int i=0; i<n-1; i++) {
        int lowindex = i; // Remember its index 
        for (int j=n-1; j>i; j--) {// Find least
            if (Comp::lt(A[j], A[lowindex])) {
                lowindex = j; // Put it in place
                }
        }
        swap(A, i, lowindex); 
    }
}
情况 时间复杂度
最好 \(O(n^2)\)
最坏 \(O(n^2)\)
平均 \(O(n^2)\)
以上三种方法都需要平均\(n(n-1)/2\)次交换

希尔排序 Shell sort

原理

希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法。

希尔排序是基于插入排序的以下两点性质而提出改进方法的：

希尔排序的基本思想是：

  1. 先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序
  2. 待整个序列中的记录“基本有序”时，再对全体记录进行依次直接插入排序。 
template <class Elem, class Comp>
void inssort2(Elem A[], int n, int incr) {
    for (int i = incr; i <n ; i+=incr) 
        for (int j = i; (j >= incr) and (Comp::lt(A[j], A[j-incr])); j--)
            swap(A, j, j-incr);
}

template <class Elem, class Comp>
void shellsort(Elem A[], int n) {
    for (int i = n/2; i > 2; i/2) // For each incr
        for  (int j = 0; j< i; j++) // sort sublists
            inssort2<ELem, Comp>(&A[j], n-j, i);
    inssort2<Elem, Comp>(A,n,1)
}

归并排序 Merge sort

原理

将数据分成两组，排序后合并；不断重复改操作

递归实现

template<class Elem,class Comp>
void mergesort(Elem A[], Elem temp[], int left, int right) {
    int mid = (left + right) / 2;
    if (left == right) return;
    mergesort<Elem, Comp>(A, temp, left, mid);
    mergesort<Elem, Comp>(A, temp, mid+1, right);
    for (int i = left; i <= right; i++)
        temp[i] = A[i];
    int i1 = left; int i2 = mid + 1;
    for (int curr = left; curr <= right; curr++) {
        if (i1 == mid + 1)
            A[curr] = temp[i2++];
        else if (i2 > right)
            A[curr] = temp[i1++];
        else if (Comp::lt(temp[i1], temp[i2]))
            A[curr] = temp[i1++];
        else A[curr] = temp[i2++];
    }
}

【施工中】非递归实现

情况 时间复杂度
最好 \(O(n\log n)\)
最坏 \(O(n\log n)\)
平均 \(O(n\log n)\)

快速排序 Quick sort

原理

分而治之思想，参照pivot将数组分成两部分，一部分小于pivot，一部分大于pivot。然后重复着一操作

递归实现

template <class Elem> int FindPivot(Elem A[], int i, int j) { return (i + j) / 2; }

// pivot is supposed to be located at the end i.e. position r by convention
template <class Elem, class Comp>
int Partition(Elem A[], int l, int r, Elem& pivot) {
    --l;
    do {
        while (Comp::lt(A[++l], pivot));
        while ((r != 0) && Comp::gt(A[--r], pivot));
        swap(A, l, r);
    } while (l < r);
    swap(A, l, r);
    return l;
}

// Initial call: QuickSort(array,0,n-1)
template <class Elem, class Comp>
void QuickSort(Elem A[], int i, int j) {
    if (j <= i) return;
    int pivotidx = FindPivot<Elem>(A, i, j);
    swap(A, pivotidx, j); // Put the pivot at the end
    int k = Partition<Elem, Comp>(A, i, j, A[j]);
    swap(A, k, j);
    QuickSort<Elem, Comp>(A, i, k - 1);
    QuickSort<Elem, Comp>(A, k + 1, j);
}

template <class Elem, class Comp>
void QuickSortDepth(Elem A[], int i, int j, int depth) {
    if (depth < 1) return;
    if (j <= i) return;
    int pivotidx = FindPivot<Elem>(A, i, j);
    swap(A, pivotidx, j); // Put the pivot at the end
    int k = Partition<Elem, Comp>(A, i, j, A[j]);
    swap(A, k, j);
    if (1 == depth) cout << "Pivot : " << A[k] << "      ";
    QuickSortDepth<Elem, Comp>(A, i, k - 1, depth - 1);
    QuickSortDepth<Elem, Comp>(A, k + 1, j, depth - 1);
}

【施工中】非递归实现

情况 时间复杂度
最好 \(O(n\log n)\)
最坏 \(O(n^2)\)
平均 \(O(n\log n)\)

堆排序 Heap sort

原理

堆/优先队列的特点是接受任意序列的输入，输出有序序列，利用这一特点可以很方便地实现排序

【施工中】实现

情况 时间复杂度
最好 \(O(n\log n)\)
最坏 \(O(n\log n)\)
平均 \(O(n\log n)\)

计数排序

原理

  1. 假设输入数据的范围是\([0, r]\) ，开辟一块大小为r的内存空间，根据输入数据的值在相应的内存空间上做标记（标记存在）
  2. 遍历内存空间，输出标记 

【施工中】实现

情况 时间复杂度
最好 \(O(n+k)\)
最坏 \(O(n+k)\)
平均 \(O(n+k)\)

桶排序 Bin sort

原理

  1. 确定数据的范围
  2. 设计很多桶，每个桶对应不同的范围
  3. 将数据归纳到不同的桶中
  4. 在桶中排序，然后合并数据



情况 时间复杂度
最好 \(O(n + k)\)
最坏 \(O(n^2)\)
平均 \(O(n + k)\)

实现

template<class Elem>
void binsort(Elem A[], int n) {
    List<Elem> B[MaxKeyValue];
    Elem item;
    for (i=0; i<n; i++) B[A[i]].append(A[i]);
    for (i=0; i< MaxKeyValue; i++)
        for (B[i].setStart(); B[i].getValue(item); B[i].next())
            output(item);
}

基数排序 Radix sort

原理

计数排序和桶排序很像，它基于数字的不同位数的规律将数字分类：

  1. 先根据最低位将数字分成十类，排序
  2. 根据第二低位排序，此时个位数都被归为一类中
  3. 以此类推





实现

template <class Elem, class Comp>
void radix(Elem A[], Elem B[], int n, int k, int r, int cnt[]) {
    int j;
    for (int i=0; rtok=1; i<k; i++, rtok*=r) {
        for (j=0; j<r; j++) cnt[j] = 0;
        for (j=0; j<n; j--) cnt[(A[j]/rtok)%r]++;
        for (j=1; j<r; j++) cnt[j] = cnt[j-1] + cnt[j];
        for (j=n-1; j>=0; j--) B[--cnt[(A[j]/rtok)%r]] = A[j];
        for (j=0; j<n; j++) A[j]=B[j];
    }
}
情况 时间复杂度
最好 \(O(k(n+r))\)
最坏 \(O(k(n+r))\)
平均 \(O(k(n+r))\)

C++ 类

定义、继承、重载、私有/公有方法、多态、构造、销毁、友元函数、重载、类指针

参考

https://www.jianshu.com/p/183eab4e56cc